package 刷题.Leedcode572;

import sun.reflect.generics.tree.Tree;

//1.两棵树都为空树，包含
//2.root为空，不包含
//3.subRoot为空，包含
//4.头结点一样，左子树和右子树都一样，用递归
//5.头结点不一样，找左孩子，一直没有找右孩子
public class Solution {
    //两棵树不完全相同的情况
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //subRoot为空，那么root必不为空，包含
        if(subRoot == null){
            return true;
        }
        //如果root为空，那么subRoot必不为空，不包含
        if(root == null){
            return false;
        }
        //递归判断左子树中是否包含，或者右子树中是否包含，或者是否两棵树完全一样
        return isSubtree(root.left,subRoot) ||
                isSubtree(root.right,subRoot) ||
                isSameTree(root,subRoot);
    }
    //判断两棵树是否相同
    public boolean isSameTree(TreeNode root,TreeNode subRoot){
        //如果两个树都为空，包含
        if(root == null && subRoot == null){
            return true;
        }
        //因为此处是判断两棵树是否相同
        //所以任一个树为空而另一个树不为空都返回false
        if(root == null || subRoot == null){
            return false;
        }
        if(root.val != subRoot.val){
            return false;
        }
        //判断是否相同，相同返回true，有一个不同就返回false
        return isSameTree(root.left,subRoot.left) &&
                isSameTree(root.right,subRoot.right);
    }
}
